1. Field of the Invention
The present invention relates to the tessellation into triangles of graphic images on a computer graphics display device. More particularly, the present invention relates to the tessellation of curved surfaces into triangles for display of the curved surface on a computer graphics display device.
2. Art Background
In the past, computer graphic systems required expensive display and computer resources. The amount of computation time required to render images was substantial. Images of any complexity required powerful computers to process for hours in order to generate the image. Today, computer graphics technology has greatly improved. The rendering of three dimensional ("3D") objects is no longer a process reserved for expensive high-powered computers. The rendering of complex graphic objects is now realized on smaller, more affordable, less powerful computers.
However, there is still the need to increase the speed of rendering and manipulating complex graphic objects without incurring substantial computer overhead and cost. The problem of rendering curved surfaces is particularly problematic. In the past, techniques were developed to render curved surfaces directly from the curved surface primitives which define the surface. See, for example, Jeffrey Lane, Loren Carpenter, Turner Whitted, James Blinn, "Scan Line Methods For Displaying Parametrically Defined Surfaces", Communications of the ACM, 23(1), January, 1980; and Sheue-Ling Lien, Michael Shantz and Vaughan Pratt, "Adaptive Forward Differencing For Rendering Curves and Surfaces", Computer Graphics, 21(4), pp 111-117, July, 1987.
It has become advantageous to divide the larger primitives into triangles, for input to the a graphics accelerator which processes the triangle. Typical graphics accelerators are characterized by having special VLSIs for rendering triangles, complemented with microprogrammable floating point processors for floating point intensive tasks.
Triangles are a natural common denominator primitive to build special VLSIs for, as the triangle is a simple primitive and higher level primitives can be reduced to the triangle primitive. However the development of a graphics accelerator having VLSIs dedicated to rendering curved surfaces is not practical. Special VLSIs for curved surfaces would be limited to a specific class of surfaces, for example cubic Bezier only and would not be able to handle all classes of curved surfaces. Therefore, it becomes essential to have a technology for the efficient tessellation of high level curved surfaces into triangles.